public class Solution {
    //买卖股票最佳时机
    public int maxProfit(int[] prices) {
        int max = 0;
        int min = 65535;
        for(int i = 0;i < prices.length;i++) {
            //当前点位卖出，与历史最小值买入之差大于最大利润，此时为最大利润
            if(prices[i] - min > max) {
                max = prices[i] - min;
            }
            //如果此时比最小值小，最小值变为当前值
            if(prices[i] < min) {
                min = prices[i];
            }
        }
        //此时拿到最大利润
        return max;
    }
    //买卖股票最佳时期||
    public int maxProfit2(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n+1][2];
        dp[1][0] = -prices[0];
        dp[1][1] = 0;
        for(int i = 2; i < n+1; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] - prices[i-1]);
            dp[i][1] = Math.max(dp[i-1][0] + prices[i-1], dp[i-1][1]);
        }
        return dp[n][1];
    }
}
